#include<iostream>

#include<vector>

using namespace std;
void dfs(int n, int pos);

int ret;
vector<int> path;
bool check[16];
int countArrangement(int n) {
    dfs(n, 1);
    return ret;
}

void dfs(int n, int pos)
{
    if (path.size() == n)
    {
        ret++;
        return;
    }
    path.push_back(pos);
    check[pos] = true;
    dfs(n, pos + 1);
    if (check[pos] == false && (path[pos-1]/pos == 0 || pos/path[pos -1] == 0))
    {
        
        path.pop_back();
        check[pos] = false;

    }
}

int main()
{
    countArrangement(2);
    return 0;
}

class Solution {
public:
    int ret;
    bool check[16];
    int countArrangement(int n) {
        dfs(n, 1);
        return ret;
    }

    void dfs(int n, int pos)
    {
        if (n + 1 == pos)
        {
            ret++;
            return;
        }
        for (int i = 1; i <= n; i++)
        {
            if (!check[i] && (pos % i == 0 || i % pos == 0))
            {
                check[i] = true;
                dfs(n, pos + 1);
                check[i] = false;
            }
        }
    }
};
